# 221 反转链表II
# https://leetcode.cn/problems/reverse-linked-list-ii/description/
# 前置题目: https://leetcode.cn/problems/reverse-linked-list/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/30
from typing import Optional

from leetcode.bds import ListNode, ListConvert
from leetcode.test import test_function as tf


def reverseBetween(head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    """我的方法"""
    head = ListNode(-1, head)
    curr = head.next
    prev = head  # 标记截取段的前一个节点
    index = 1
    while curr and index <= right:
        if index == left - 1:
            prev = curr
        if index == right:
            end = curr.next  # 标记截取段的后一个节点
            curr = prev.next
            l = end
            while curr != end:
                r = curr.next
                curr.next = l
                l, curr = curr, r
            prev.next = l
            return ListConvert.link_to_list(head.next)
        index += 1
        curr = curr.next


def reverseBetween_opt(head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    p0 = dummy = ListNode(next=head)
    for _ in range(left - 1):
        p0 = p0.next

    pre = None
    cur = p0.next
    for _ in range(right - left + 1):
        nxt = cur.next
        cur.next = pre  # 每次循环只修改一个 next，方便大家理解
        pre = cur
        cur = nxt

    p0.next.next = cur
    p0.next = pre
    return ListConvert.link_to_list(dummy.next)


if __name__ == '__main__':
    head1 = ListConvert.list_to_link([1, 2, 3, 4, 5])
    head2 = ListConvert.list_to_link([5])
    head3 = ListConvert.list_to_link([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
    head4 = ListConvert.list_to_link([3, 5])
    head5 = ListConvert.list_to_link([1, 2, 3, 4])
    inp = [{"head": head1, "left": 2, "right": 4}, {"head": head2, "left": 1, "right": 1},
           {"head": head3, "left": 5, "right": 9}, {"head": head4, "left": 1, "right": 2},
           {"head": head5, "left": 1, "right": 4}, ]
    out = [[1, 4, 3, 2, 5], [5], [1, 2, 3, 4, 9, 8, 7, 6, 5, 10], [5, 3], [4, 3, 2, 1]]

    tf(reverseBetween, inp, out, times=1000)
    tf(reverseBetween_opt, inp, out, times=1000)
